/**
 * 这个问题可以通过二分查找结合广度优先搜索（BFS）来解决。
 * 我们需要确定配送员的防护能力，以便找到可以在不超过 K 单位时间内从左上角移动到右下角的路径。
 * 
 * 问题步骤：
 * 辐射值范围：
 *      首先确定迷宫中的辐射值的范围。
 *      然后使用二分查找来找出最小的辐射值，使得配送员可以在不超过 K 单位时间内完成任务。
 * BFS 检查路径：
 *      对于每个辐射值，我们使用 BFS 来检查是否存在一条路径，从左上角到右下角，
 *      且沿途经过的格子的辐射值不超过当前的防护能力，并且总时间不超过 K。
 */



function canReach(maze, N, K, radiation) {
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const queue = [[0, 0, 0]]; // [x, y, time]
    const visited = Array.from({ length: N }, () => Array(N).fill(false));

    if (maze[0][0] > radiation || maze[N - 1][N - 1] > radiation) {
        return false; // Start or end radiation too high
    }

    visited[0][0] = true;

    while (queue.length > 0) {
        const [x, y, time] = queue.shift();

        // Check if we reached the bottom-right corner
        if (x === N - 1 && y === N - 1) {
            return time <= K;
        }

        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;

            if (nx >= 0 && ny >= 0 && nx < N && ny < N &&
                !visited[nx][ny] && maze[nx][ny] <= radiation) {
                visited[nx][ny] = true;
                queue.push([nx, ny, time + 1]);
            }
        }
    }
    return false;
}

function minRadiation(N, K, maze) {
    let low = 0;
    let high = Math.max(...maze.flat());
    let result = -1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (canReach(maze, N, K, mid)) {
            result = mid; // Found a valid radiation level
            high = mid - 1; // Try for a smaller radiation level
        } else {
            low = mid + 1; // Increase the radiation level
        }
    }

    return result;
}

// 示例输入
const N = 5;
const K = 8;
const maze = [
    [0, 0, 0, 0, 0],
    [9, 9, 3, 9, 0],
    [0, 0, 0, 0, 0],
    [0, 9, 5, 9, 9],
    [0, 0, 0, 0, 0]
];

console.log(minRadiation(N, K, maze)); // 输出: 3